
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1596. -- [Usaco2008 Jan]电话网络 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1596: [Usaco2008 Jan]电话网络</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>220&nbsp;&nbsp;<span class=green>Solved: </span>105<br>[<a href='submitpage.php?id=1596'>Submit</a>][<a href='problemstatus.php?id=1596'>Status</a>][<a href='bbs.php?id=1596'>Discuss</a>]</center><h2>Description</h2><div class=content>    Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。
不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上
无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N
顺次编号。

    所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 
1 <= B <= N; A != B)，都可以找到一个以A开头以B结尾的草地序列，并且序列
中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上，一座塔的服务
范围为它所在的那块草地，以及与那块草地相邻的所有草地。

    请你帮FJ计算一下，为了建立能覆盖到所有草地的通信系统，他最少要建
多少座无线电通讯塔。

</div><h2>Input</h2><div class=content>* 第1行: 1个整数，N

* 第2..N行: 每行为2个用空格隔开的整数A、B，为两块相邻草地的编号

</div><h2>Output</h2><div class=content>* 第1行: 输出1个整数，即FJ最少建立无线电通讯塔的数目

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5<br />
1 3<br />
5 2<br />
4 3<br />
3 5<br />
<br />
输入说明:<br />
<br />
    Farmer John的农场中有5块草地：草地1和草地3相邻，草地5和草地2、草地<br />
4和草地3，草地3和草地5也是如此。更形象一些，草地间的位置关系大体如下：<br />
（或是其他类似的形状）<br />
               4  2<br />
               |  |<br />
            1--3--5<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2<br />
<br />
输出说明:<br />
<br />
    FJ可以选择在草地2和草地3，或是草地3和草地5上建通讯塔。<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1596'>Submit</a>][<a href='problemstatus.php?id=1596'>Status</a>][<a href='bbs.php?id=1596'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
